package hot;

import java.util.ArrayList;
import java.util.List;

public class erer {


//    https://leetcode.cn/problems/generate-parentheses/?envType=study-plan-v2&envId=top-100-liked
    class Solution {
        List<String>  ret=new ArrayList<>();
        StringBuffer path=new StringBuffer();
        int m;
        int left=0;
        int right=0;
        public List<String> generateParenthesis(int n) {
            m=n;
            dfs();
            return ret;
        }
        public void dfs(){
            if(right==m){
                ret.add(String.valueOf(path));
                return;
            }
            //如果左括号可以添加
            if(left<m){
                path.append('(');
                left++;
                dfs();
                //恢复现场
                path.deleteCharAt(path.length()-1);
                left--;
            }
            //如果右括号可以添加
            if(right<left){
                path.append(')');
                right++;
                dfs();
                //恢复现场
                path.deleteCharAt(path.length()-1);
                right--;
            }
        }
    }
}
